package com.huangyi;

public class Main {
    public static void main(String[] args) {
        // 测试用例
    }

    // 最长回文子串
    static class Solution {
        public String longestPalindrome(String s) {
            int n = s.length();
            if (n < 2) return s;  // 边界处理

            char[] ch = s.toCharArray();
            boolean[][] dp = new boolean[n][n];
            int begin = 0, len = 1;  // 初始化：至少有单字符

            // 填表：i 倒序，j 正序
            for (int i = n-1; i >= 0; i--) {
                for (int j = i; j < n; j++) {
                    if (ch[i] == ch[j]) {
                        // 首尾字符相等
                        if (i == j) {
                            dp[i][j] = true;  // 单字符
                        } else if (i+1 == j) {
                            dp[i][j] = true;  // 相邻字符
                        } else {
                            dp[i][j] = dp[i+1][j-1];  // 看内部
                        }
                    }
                    // 首尾不等，保持 false

                    // 更新最长回文
                    if (dp[i][j] && j-i+1 > len) {
                        begin = i;
                        len = j-i+1;
                    }
                }
            }

            return s.substring(begin, begin + len);
        }
    }
}